Transformations of node‐balanced routing problems

This article describes a polynomial transformation for a class of unit‐demand vehicle routing problems, named node‐balanced routing problems (BRP), where the number of nodes on each route is restricted to be in an interval such that the workload across the routes is balanced. The transformation is general in that it can be applied to single or multiple depot, homogeneous or heterogeneous fleet BRPs, and any combination thereof. At the heart of the procedure lies transforming the BRP into a generalized traveling salesman problem (TSP), which can then be transformed into a TSP. The transformed graph exhibits special properties which can be exploited to significantly reduce the number of arcs, and used to construct a formulation for the resulting TSP that amounts to no more than that of a constrained assignment problem. Computational results on a number of instances are presented. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 370–387, 2015     

面向片上网络的多播吞吐率和能量模型

片上网络逐渐成为片上众核中非常有前景的互连方式.基于目录的cache一致性协议的维护需要片上互连网络高效的支持多播.在借鉴单播的网络吞吐率模型基础上,建立了面向多播的网络吞吐率模型和体系结构级的能量模型.相对于传统的多播路由算法,负载平衡维序路由算法(BDoR)和最小路径维序路由算法(MPDoR)通过平衡X和Y两个方向...     

Network routing for insurgency: An adversarial risk analysis framework

Problems in counterterrorism and corporate competition have prompted research that attempts to combine statistical risk analysis with game theory in ways that support practical decision making. This article applies these methods of adversarial risk analysis to the problem of selecting a route through a network in which an opponent chooses vertices for ambush. The motivating application is convoy routing across a road network when there may be improvised explosive devices and imperfect intelligence about their locations. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

求最大数目不相交多约束QoS路由的一种新方法

针对多约束QoS路由问题中从资源点到目的点的最大数目的不相交路由,文章给出了一种基于罚函数与整数规划的求满足QoS约束的最大数目的互不相交路由算法。该算法利用了路由模型的结构特性,使整数规划问题转化为线性规划问题,初步的算例表明算法是有效的。     

无线传感器网络动态汇聚节点调度算法研究

移动汇聚节点调度是传感器网络中一个新的研究热点.通过建立一个普适的多目标优化模型,提出了贴近实际的汇聚节点循环路径规划模型,采用以连续时间离散化为理论基础的时域-空域转化方法,将时域中的优化模型无损地转至空域中,从而大大减少了所涉及的变量数量,降低了求解的复杂度.通过实验可以看出,调度移动汇聚节点可以有效扩展网络的生命周期.     

MANET多路径路由中最大可靠性路径选择算法

如何选择路径的数量和质量对多路径路由机制的性能有着重要的影响。已有的多路径算法没有深入研究如何选择多路径的问题。对目前存在的两个典型问题进行了分析,在此基础上研究了路径可靠性模型和虚拟完全非交叉多路径模型,然后提出一个最大可靠性多路径选择算法。算法利用路径权重作为路径可靠性的近似解决方案,以此克服路径可靠性度量问题(NP难题)研究的复杂性,根据路径可靠性模型和完全非交叉多路径模型来选择可靠的路径集,使用这组路径集并行分布流量。应用OPNET模拟平台实现了算法,结果表明,本算法能增加聚合带宽,优化网络带宽的应用,提高网络的吞吐率和多路径路由的性能。     

支持QoS的无线Mesh网络机会路由优化算法

针对空中骨干Mesh网络资源有限、计算能力相对不足的特点以及传统简单机会路由(Simple Opportunistic Adaptive Routing,SOAR)路由算法未充分考虑负载均衡与不同业务服务质量(Quality of Service,Qo S)保障需求差异性的问题,提出一种支持业务区分的改进型SOAR路由算法。该算法在考虑链路拥塞控制和负载均衡的基础上,定义综合预期传输次数来描述链路的综合状态,有效降低网络拥塞概率;同时根据传输业务类型的不同,设计一种基于层次分析法的路由选择策略,实现路径选择与业务类型的动态匹配。仿真结果表明,在重负载条件下,改进型SOAR路由算法相比传统SOAR路由算法其时延、吞吐量和吞吐率性能明显提升。当网络中存在不同类型业务时,改进型SOAR路由算法能够根据业务Qo S保障需求的差异性自适应选择最佳传输路径。     

战术移动自组织网络路由方法

战术移动自组织网络(Mobile Ad Hoc Network,MANET)作为网络中心战的重要组成,有望解决未来战场上传统作战力量与新型无人作战平台之间高效组网通信问题。战术MANET作为MANET在战场环境下的应用,可在基础设施缺乏或遭破坏的地域快速展开,具有节点自由出入、移动性高、抗毁伤性强等特点。综述了战术MANET路由协议和仿真方法,对研究方法和面临的挑战作了简要评述。     

基于节点综合效能的DTN路由算法

针对容忍延迟网络(DTN)高延迟、数据传输成功率低等问题,提出了一种基于节点综合效能的DTN路由算法SERA。该算法综合考虑移动节点的活跃度和剩余能量,使消息副本向综合效能高的节点扩散。SERA节点活跃度描述了节点的社会和动态特性,SERA尽量将消息副本传递给活跃度高的节点,以提高消息传输的成功率;在选择中继节点时,充分考虑节点的能量状态,以避免能量不足的节点承担更多的信息传输任务,从而提高网络节点的存活率。仿真结果表明,与典型的DTN路由算法相比,SERA能够更好地平衡节点的能耗,获得更高的消息递交成功率和更长的网络生存期。     

直接网络中的自适应路由算法分析

互连网络是大规模并行计算机的重要组成部分，路由算法是其中决定网络性能的重要因素，本文在直接网络结构基础上对路由算法进行讨论，给出了一种分类方法，并着重对采用虫孔路由开关技术的自适应路由算法进行分析，为进一步的评价和设计新的算法提供了参考。